package com.zdj;

import java.util.Arrays;

/**
 * @author zhangdj
 * @date 2021-10-05 16:26:49
 * 快速排序
 * 找基准元素的位置，一个基准元素比较n-1次，n个基准元素比较 n(n-1)次
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arrays = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
        quickSort(arrays, 0, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 快速排序
     *
     * @param arrays 要排序的数组
     * @param low    数组开始索引
     * @param high   数组最终索引
     */
    public static void quickSort(int[] arrays, int low, int high) {
        if (arrays == null || arrays.length < 2) {
            return;
        }
        if (low >= high) {
            return;
        }
        int i = low;
        // 基准
        int temp = arrays[low];
        while (low < high) {
            // 当队尾元素大于基准元素时，索引减1
            while (low < high && arrays[high] >= temp) {
                high--;
            }
            // 从后往前，如果high的值小于基准值，则将height的值赋值给low
            arrays[low] = arrays[high];
            // 当对前元素小于基准元素时，索引加1
            while (low < high && arrays[low] <= temp) {
                low++;
            }
            // 从前往后，如果low元素的值大于基准元素，则将low元素的值复制给high
            arrays[high] = arrays[low];
        }
        arrays[low] = temp;
        // 递归排序左边
        quickSort(arrays, i, low - 1);
        // 递归排序右边
        quickSort(arrays, low + 1, high);
    }
}
